package features.advance.leetcode.linkedlist.medium;

import java.util.HashMap;
import java.util.Map;

/**
 *  剑指 Offer 35. 复杂链表的复制
 *
 *  难度：简单
 *
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
 * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 示例 2：
 *
 *
 *
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * 示例 3：
 *
 *
 *
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * 示例 4：
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *
 *
 * 提示：
 *
 * -10000 <= Node.val <= 10000
 * Node.random 为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 *
 *
 * 注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 *
 * @author LIN
 * @date 2021-06-09
 */
public class Offer35 {
    public static void main(String[] args) {
        Solution solution = new Solution() {
            /**
             * 方法二：拼接、拆分
             * @param head
             * @return Node
             */
            @Override
            public Node copyRandomList(Node head) {
                if(head == null) return null;
                Node cur = head;
                /*
                生成重复的链表，前后节点相同
                 */
                while(cur != null){
                    Node node = new Node(cur.val);
                    node.next = cur.next;
                    cur.next = node;
                    cur = node.next;
                }
                cur = head;
                /*
                 复制random指向
                 */
                while(cur != null){
                    if(cur.random!=null){
                        cur.next.random = cur.random.next;
                    }
                    cur = cur.next.next;
                }
                /*
                 拆分链表
                 */
                Node pre = head;
                cur = pre.next;
                Node res = cur;
                while(cur.next != null){
                    pre.next = pre.next.next;
                    cur.next = cur.next.next;
                    pre = pre.next;
                    cur = cur.next;
                }
                pre.next = null;
                return res;
            }
        };
        Node head = new Node(7);
        Node node = new Node(13);
        head.next = node;
        Node node1 = new Node(11);
        node.next = node1;
        node.random = head;
        Node node2 = new Node(10);
        node1.next = node2;
        Node node3 = new Node(1);
        node1.random = node3;
        node2.next = node3;
        node3.random = head;
        node2.random = node1;
        Node node4 = solution.copyRandomList(head);
    }
    static class Solution {
        /*
        哈希表法，遍历两遍，时间复杂度O(N)，空间复杂度O(N)
         */
        public Node copyRandomList(Node head) {
            Map<Node ,Node> dic  = new HashMap();
            Node cur = head;
            while(cur != null){
                dic.put(cur,new Node(cur.val));
                cur = cur.next;
            }

            cur = head;
            while(cur != null){
                dic.get(cur).next = dic.get(cur.next);
                dic.get(cur).random = dic.get(cur.random);
                cur = cur.next;
            }
            return  dic.get(head);
        }
    }

    // Definition for a Node.
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
